package com.zgkxzx.数据结构.树.二叉树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 创建者   zgkxzx
 * 创建日期 2018/5/7.
 * 功能描述 二叉树
 */
public class BinaryTree2 {
    private Node root;

    public BinaryTree2() {
    }

    /**
     * 插入一个节点
     *
     * @param key
     */
    public void insertNode(int key) {
        //1,如果节点为空的情况
        if (root == null) {
            root = new Node(key);
            return;
        }
        //2,
        Node currentNode = root;
        while (currentNode != null) {
            if (key < currentNode.key) {
                if (currentNode.leftNode == null) {
                    currentNode.leftNode = new Node(key);
                    return;
                } else
                    currentNode = currentNode.leftNode;
            } else {
                if (currentNode.rightNode == null) {
                    currentNode.rightNode = new Node(key);
                    return;
                } else
                    currentNode = currentNode.rightNode;
            }
        }
    }


    public int delete(int key) {
        //Node node = findParent(key);
        Node currentNode = root;
        Node parentNode = root;
        boolean isLeftChild = true;

        while (key != currentNode.key) {
            parentNode = currentNode;
            if (key < currentNode.key) {
                currentNode = currentNode.leftNode;
                isLeftChild = true;
            } else if (key > currentNode.key) {
                currentNode = currentNode.rightNode;
                isLeftChild = false;
            }
            if (currentNode == null)
                return -1;
        }


        //如果左右两个子节点都为空 ，直接删除此节点
        if (currentNode.rightNode == null && currentNode.leftNode == null) {
            if (currentNode == root)
                root = null;
            else if (isLeftChild)
                parentNode.leftNode = null;
            else
                parentNode.rightNode = null;
        } else if (currentNode.rightNode == null && currentNode.leftNode != null) {
            if (currentNode == root)
                root = currentNode.leftNode;
            else if (isLeftChild)
                parentNode.leftNode = currentNode.leftNode;
            else
                parentNode.rightNode = currentNode.leftNode;
        } else if (currentNode.rightNode != null && currentNode.leftNode == null) {
            if (currentNode == root)
                root = currentNode.rightNode;
            else if (isLeftChild)
                parentNode.leftNode = currentNode.rightNode;
            else
                parentNode.rightNode = currentNode.rightNode;
        } else {

            Node successor = getSuccessor(currentNode);
            if (currentNode == root) {
                //这里要先从root上删除这个后继节点
                delete(successor.key);
                root = successor;
                successor.rightNode = currentNode.rightNode;
            } else if (isLeftChild)
                parentNode.leftNode = successor;
            else
                parentNode.rightNode = successor;
            successor.leftNode = currentNode.leftNode;

        }

        return 0;

    }

    private Node getSuccessor(Node node) {
        Node currentNode = node.rightNode;
        Node preNode = currentNode;
        while (currentNode != null) {
            preNode = currentNode;
            currentNode = currentNode.leftNode;
        }
        return preNode;
    }



    public Node find(int key) {
        Node currentNode = root;
        while (currentNode != null) {
            if (key < currentNode.key) {
                currentNode = currentNode.leftNode;
            } else if (key > currentNode.key) {
                currentNode = currentNode.rightNode;
            } else {
                return currentNode;
            }

        }
        return null;
    }


    public void prePrint() {
        prePrint(root);
    }


    public void prePrint(Node node) {
        System.out.println(node);
        if (node.leftNode != null)
            prePrint(node.leftNode);
        if (node.rightNode != null)
            prePrint(node.rightNode);
    }

    public void print() {
        /*Node currentNode = root;
        //Stack<Node> stack = new Stack<>();
        Queue<Node> queue = new LinkedBlockingQueue<>();
        if (currentNode != null)
            queue.add(currentNode);

        int i = 0;
        while (!queue.isEmpty()) {

            Node node = queue.poll();
           // System.out.println("第" + i++ + "层 " + node);


            if (node.leftNode != null)
                queue.add(node.leftNode);
            if (node.rightNode != null)
                queue.add(node.rightNode);
        }*/

        print(root);

    }

    public static void print(Node root) {
        // 创建一个队列用来存放节点
        Queue<Node> queue = new LinkedList<Node>();
        // 当前行打印的最右节点
        Node last;
        // 下一行打印的最右节点
        Node nlast = null;
        last = root;
        // 先将根放入队列中
        queue.add(root);
        // 队列不为空时，就一直循环poll直到队列为空
        while (queue.size() > 0) {
            // 推出节点
            Node nowTree = queue.poll();
            // 如果当前节点有左节点，将左节点压入队列中
            if (nowTree.leftNode != null) {
                queue.add(nowTree.leftNode);
                nlast = nowTree.leftNode;
            }
            // 如果当前节点有右节点，将左节点压入队列中
            if (nowTree.rightNode != null) {
                queue.add(nowTree.rightNode);
                nlast = nowTree.rightNode;
            }
            System.out.print("  " + nowTree.key);
            // 当当前打印节点为当前行最右节点时换行
            if (last.equals(nowTree)) {
                System.out.println();
                last = nlast;
            }
        }

    }


    private static class Node {
        public int key;
        public Node leftNode;
        public Node rightNode;

        public Node(int key) {
            this.key = key;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    '}';
        }
    }
}
